package LeetCode_力扣;
//面试题 02.04. 分割链表
//要求： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
// 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要保留每个分区中各节点的初始相对位置。
//

/**
 * 思路一：创建两个新链表。这两个链表就是由原链表组成的。
 * 一个链表存放小于 x 的节点。
 * 一个链表存放大于等于 x 的节点
 * 然后小链表连接大链表就成功了。
 */

/*

public class partition_02_04 {
    public ListNode partition(ListNode head, int x) {

        //判一下空
        if(head == null || head.next == null){
            return head;
        }

        //存放小于x的链表
        ListNode dummyHead1 = new ListNode(0);
        ListNode prve1 = dummyHead1;//尾节点，用于连接

        //存放大于等于x的链表
        ListNode dummyHead2 = new ListNode(0);
        ListNode prve2 = dummyHead1;//尾节点，用于连接

        while(head != null){
            if(head.val < x){
                prve1.next = head;
                prve1 = prve1.next;
                head = head.next;

                prve1.next = null;//切断后面的连接

            }else{
                prve2.next = head;
                prve2 = prve2.next;
                head = head.next;

                prve2.next = null;//切断后面的连接

            }
        }
        prve1.next = dummyHead2.next;

        return dummyHead1.next;

    }
}

 */










//public class partition_02_04 {
//    public ListNode partition(ListNode head, int x) {
//
//    }
//}



//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode(int x) {
//        val = x;
//    }
//}
